package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         103,
		Discription: "二叉树的锯齿层序遍历（每一层一起输出，隔层反序）",
		Level:       2,
		Labels: map[string]int{
			"队列":  1,
			"二叉树": 1,
		},
	})
}

func ZigzagLevelOrder(root *ds.TreeNode) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}

	q := []*ds.TreeNode{root}
	reverse := false
	for len(q) > 0 {
		count := len(q)
		column := make([]int, 0)
		for i := 0; i < count; i++ {
			//维护一个是否反序的变量，反序时倒着append
			if reverse {
				column = append([]int{q[i].Val}, column...)
			} else {
				column = append(column, q[i].Val)
			}

			if q[i].Left != nil {
				q = append(q, q[i].Left)
			}
			if q[i].Right != nil {
				q = append(q, q[i].Right)
			}
		}

		//反转reverse
		reverse = !reverse
		q = q[count:]
		res = append(res, column)
	}

	return res
}
